1
Principios de Minimización Sin Restricciones
MATH008Lesson 9
00:00
Pasamos de la existencia teórica de un mínimo al motor algorítmico de la optimización. Nuestro objetivo principal es minimizar $f(x)$ (9.1) donde $f: \mathbf{R}^n \to \mathbf{R}$ es convexa y dos veces continuamente diferenciable. Dado que $f$ es diferenciable y convexa, una condición necesaria y suficiente para que un punto $x^*$ sea óptimo es $\nabla f(x^*) = 0$.

El Marco Algorítmico

Las soluciones numéricas construyen una secuencia minimizadora: Una secuencia de puntos $x^{(0)}, x^{(1)}, \dots \in \text{dom } f$ con $f(x^{(k)}) \to p^*$ cuando $k \to \infty$. Cada paso actualiza la posición mediante $x^{(k+1)} = x^{(k)} + t^{(k)}\Delta x^{(k)}$, donde $\Delta x$ es una dirección descendente.

Inicialización y Convergencia

Los métodos descritos en este capítulo requieren un punto de inicio adecuado $x^{(0)}$. El punto de inicio debe pertenecer a $\text{dom } f$, y además el conjunto de nivel inferior $S = \{x \in \text{dom } f \mid f(x) \le f(x^{(0)})\}$ debe ser cerrado. Esto garantiza que la secuencia permanezca en una región bien comportada donde el hessiano proporciona información útil.

Direcciones de Descenso

La dirección más simple es $\Delta x = -\nabla f(x)$. Sin embargo, la eficiencia a menudo requiere tener en cuenta diferentes geometrías mediante la dirección de descenso más pronunciado:

  • Norma Cuadrática: $\|z\|_P = (z^T P z)^{1/2} = \|P^{1/2}z\|_2$.
  • Norma $L_\infty$: $\Delta x_{\text{sd}} = \Delta x_{\text{nsd}} \|\nabla f(x)\|_\infty = - \frac{\partial f(x)}{\partial x_i} e_i$ (Descenso por Coordenadas).

Modelos de Segundo Orden y Regiones de Confianza

El método de Newton utiliza una aproximación de Taylor de segundo orden: $$\hat{f}(x+v) = f(x) + \nabla f(x)^T v + \frac{1}{2} v^T \nabla^2 f(x) v$$ Esta cuadrática se minimiza cuando $v = \Delta x_{nt}$ (el paso de Newton). Definimos una región de confianza: el conjunto $\{v \mid \|v\|_2 \le \gamma\}$. El parámetro $\gamma$ refleja nuestra confianza en el modelo de segundo orden. Cuando el modelo es preciso, resolvemos la dirección mediante $v = L^{-T}w = -L^{-T}L^{-1}P^T g$ en sistemas de KKT.

🎯 Principios Fundamentales de Convergencia
La eficiencia se mide por la velocidad a la que desaparece el error $f(x^{(k)}) - p^*$. Para funciones fuertemente convexas, el error $f(x^{(k)}) - p^*$ converge a cero al menos tan rápido como una serie geométrica. En el contexto de métodos numéricos iterativos, esto se llama convergencia lineal.
  • Cota de Suboptimalidad: $p^* \geq f(x) + \lambda(x) + \log(1 - \lambda(x))$, válida si $\lambda(x) < 1$.
  • Suma de Autoconcordancia: Si $f_1, f_2$ son autoconcordantes, entonces $f_1 + f_2$ es autoconcordante.
  • Dispersión del Hessiano: Se gana eficiencia si la condición de estructura de banda del hessiano: $\nabla^2 f(x)_{ij} = 0$ para $|i-j| > k$ se cumple.